import java.util.LinkedList;
import java.util.List;

public class Offer_34 {
    /**
     * 剑指 Offer 34. 二叉树中和为某一值的路径
     * 输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
     * <p>
     * 示例:
     * 给定如下二叉树，以及目标和 target = 22，
     * <p>
     * 5
     * / \
     * 4   8
     * /   / \
     * 11  13  4
     * /  \    / \
     * 7    2  5   1
     * 返回:
     * <p>
     * [
     * [5,4,11,2],
     * [5,8,4,5]
     * ]
     */
    List<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        preOrder(root, target);
        return res;
    }

    private void preOrder(TreeNode root, int target) {
        if (root == null) {
            return;
        }
        int val = root.val;
        target -= val;
        path.add(val);
        if (target == 0 && root.left == null && root.right == null) {
            res.add(new LinkedList(path));
        }
        if (root.left != null)
            preOrder(root.left, target);
        if (root.right != null)
            preOrder(root.right, target);
        path.removeLast();
    }

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(1);
        TreeNode treeNode1 = new TreeNode(2);
        TreeNode treeNode2 = new TreeNode(3);
        treeNode.left = treeNode1;
        treeNode.right = treeNode2;
        Offer_34 offer = new Offer_34();
        List<List<Integer>> lists = offer.pathSum(treeNode, 3);

        for (List<Integer> tempList :
                lists) {

                System.out.println(tempList);

        }
    }
}
